{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Plus One"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: plusOne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #加一"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由 <strong>整数 </strong>组成的<strong> 非空</strong> 数组所表示的非负整数，在该数的基础上加一。</p>\n",
    "\n",
    "<p>最高位数字存放在数组的首位， 数组中每个元素只存储<strong>单个</strong>数字。</p>\n",
    "\n",
    "<p>你可以假设除了整数 0 之外，这个整数不会以零开头。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [1,2,3]\n",
    "<strong>输出：</strong>[1,2,4]\n",
    "<strong>解释：</strong>输入数组表示数字 123。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [4,3,2,1]\n",
    "<strong>输出：</strong>[4,3,2,2]\n",
    "<strong>解释：</strong>输入数组表示数字 4321。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [0]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= digits.length <= 100</code></li>\n",
    "\t<li><code>0 <= digits[i] <= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [plus-one](https://leetcode.cn/problems/plus-one/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [plus-one](https://leetcode.cn/problems/plus-one/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[4,3,2,1]', '[9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num=[]\n",
    "        p=head\n",
    "        while p!=None:\n",
    "            num.append(str(p.val))\n",
    "            p=p.next\n",
    "        num=int(''.join(num))+1\n",
    "        p=head\n",
    "        last=None\n",
    "        for char in str(num):\n",
    "            if p==None:\n",
    "                p=ListNode(val=char)\n",
    "                last.next=p\n",
    "            else:\n",
    "                last=p\n",
    "                p.val=char\n",
    "                p=p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 快慢指针\n",
    "        slow = ListNode()\n",
    "        slow.next = fast = head\n",
    "        while fast:\n",
    "            if fast.val != 9:\n",
    "                slow = fast\n",
    "            fast = fast.next\n",
    "        slow.val += 1\n",
    "        cur = slow.next\n",
    "        while cur:\n",
    "            cur.val = 0\n",
    "            cur = cur.next\n",
    "        return slow if slow.next == head else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                cur = head\n",
    "            head = head.next\n",
    "        \n",
    "        cur.val +=1\n",
    "        cur = cur.next\n",
    "        while cur:\n",
    "            cur.val = 0\n",
    "            cur = cur.next\n",
    "        \n",
    "        if dummy.val == 0:\n",
    "            return dummy.next\n",
    "        else:\n",
    "            return dummy\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "        \n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        root = head\n",
    "        stack = []\n",
    "\n",
    "        while root:\n",
    "            stack.append(root)\n",
    "            root = root.next\n",
    "\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.val == 9:\n",
    "                node.val = 0\n",
    "            else:\n",
    "                node.val += 1\n",
    "                return head\n",
    "        return ListNode(1, next=head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution(object):\n",
    "    def plusOne(self, head):\n",
    "        st = []\n",
    "        while head:\n",
    "            st.append(head.val)\n",
    "            head = head.next\n",
    "        carry = 0\n",
    "        dummy = ListNode(0)\n",
    "        adder = 1\n",
    "        while st or adder!=0 or carry>0:\n",
    "            digit =st.pop() if st else 0\n",
    "            #print(digit,adder)\n",
    "            carry+=(digit+adder)\n",
    "            cur=ListNode(carry%10)\n",
    "            carry//=10\n",
    "            cur.next=dummy.next\n",
    "            dummy.next=cur\n",
    "            adder=0\n",
    "        return dummy.next\n",
    "        # while st or adder != 0 or carry > 0:\n",
    "        #     digit = st.pop() if st else 0\n",
    "        #     sum = digit + adder + carry\n",
    "        #     carry = 1 if sum >= 10 else 0\n",
    "        #     sum = sum - 10 if sum >= 10 else sum\n",
    "        #     cur = ListNode(sum)\n",
    "        #     cur.next = dummy.next ### 把创造好的节点往前加\n",
    "        #     dummy.next = cur\n",
    "        #     adder = 0\n",
    "        # return dummy.next\n",
    "\n",
    "# 作者：负雪明烛\n",
    "# 链接：https://leetcode.cn/problems/plus-one-linked-list/solutions/1077267/fu-xue-ming-zhu-qiu-jia-fa-xiang-xi-tu-j-rrs3/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(0,head)\n",
    "        prev = dummy\n",
    "\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                prev = head\n",
    "            head = head.next\n",
    "        \n",
    "        prev.val += 1\n",
    "        prev = prev.next\n",
    "\n",
    "        while prev:\n",
    "            prev.val = 0\n",
    "            prev = prev.next\n",
    "        \n",
    "        return dummy if dummy.val else dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        st=[]\n",
    "        while head:\n",
    "            st.append(head.val)\n",
    "            head=head.next\n",
    "        carry=0\n",
    "        dummy=ListNode(0)\n",
    "        adder=1\n",
    "        while st or adder!=0 or carry>0:\n",
    "            digit=st.pop() if st else 0\n",
    "            sum=digit+adder+carry\n",
    "            carry=1 if sum>=10 else 0\n",
    "            sum=sum-10 if sum>=10 else sum\n",
    "            cur=ListNode(sum)\n",
    "            cur.next=dummy.next\n",
    "            dummy.next=cur\n",
    "            adder=0\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        adr = []\n",
    "        tmp = head\n",
    "        while tmp != None:\n",
    "            adr.append(tmp)\n",
    "            tmp = tmp.next\n",
    "        \n",
    "        idx = len(adr) - 1\n",
    "        while True:\n",
    "            adr[idx].val = (adr[idx].val + 1) % 10\n",
    "            if adr[idx].val != 0:\n",
    "                break\n",
    "            elif adr[idx].val == 0 and idx == 0:\n",
    "                NewHead = ListNode(1, adr[0])\n",
    "                return NewHead\n",
    "            idx -= 1\n",
    "        return head                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        c = [0]\n",
    "        \n",
    "        def backtrack(head):\n",
    "            if not head.next:\n",
    "                [c[0],head.val] = divmod((head.val+1),10)\n",
    "                return \n",
    "            backtrack(head.next)\n",
    "            [c[0],head.val] = divmod((head.val+c[0]),10)\n",
    "        backtrack(head)\n",
    "        res = ListNode()\n",
    "        if c[0]==1:\n",
    "            temp = ListNode(1)\n",
    "            temp.next = head\n",
    "            res.next = temp\n",
    "        else:\n",
    "            res.next = head\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num = 0\n",
    "        while head:\n",
    "            num = num * 10 + head.val\n",
    "            head = head.next\n",
    "        num += 1\n",
    "        lst = []\n",
    "        while num:\n",
    "            lst.append(num % 10)\n",
    "            num //= 10\n",
    "        ans = node = ListNode()\n",
    "        while lst:\n",
    "            #node.val = lst.pop()\n",
    "            node.next = ListNode(lst.pop())\n",
    "            node = node.next\n",
    "        return ans.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        def change(head):\n",
    "            pre = None\n",
    "            while head:\n",
    "                next = head.next\n",
    "                head.next = pre\n",
    "                pre = head\n",
    "                head = next\n",
    "            return pre\n",
    "        head = change(head)\n",
    "        cur = head\n",
    "        up = 1\n",
    "        while cur and cur.next:\n",
    "            up += cur.val\n",
    "            cur.val = up%10\n",
    "            up //= 10\n",
    "            cur = cur.next\n",
    "        up += cur.val\n",
    "        cur.val = up%10\n",
    "        up //= 10\n",
    "        if up:\n",
    "            cur.next = ListNode(up)\n",
    "        return change(head)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num = 0\n",
    "        while head:\n",
    "            num *= 10\n",
    "            num += head.val \n",
    "            head = head.next \n",
    "        num += 1\n",
    "        newHead = ListNode(0)\n",
    "        endnode = newHead\n",
    "        for j in str(num):\n",
    "            cur = ListNode(int(j))\n",
    "            endnode.next = cur \n",
    "            endnode = cur \n",
    "        return newHead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num=[]\n",
    "        p=head\n",
    "        while p!=None:\n",
    "            num.append(str(p.val))\n",
    "            p=p.next\n",
    "        num=int(''.join(num))+1\n",
    "        p=head\n",
    "        last=None\n",
    "        for char in str(num):\n",
    "            if p==None:\n",
    "                p=ListNode(val=char)\n",
    "                last.next=p\n",
    "            else:\n",
    "                last=p\n",
    "                p.val=char\n",
    "                p=p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # Step 1: Reverse the linked list\n",
    "        prev = None\n",
    "        current = head\n",
    "        while current is not None:\n",
    "            next_node = current.next # 保存当天节点的下一个节点\n",
    "            current.next = prev   # 将当前节点的下一个节点指向前一个节点，实现逆序\n",
    "            prev = current       # 更新前一个节点为当前节点\n",
    "            current = next_node  # 更新当前节点为下一个节点\n",
    "        reversed_head = prev     # 逆序后的链表头部\n",
    "\n",
    "        # Step 2: Add one and handle carry\n",
    "        current = reversed_head    # 重头开始遍历逆序后的链表\n",
    "        carry = 1    # 初始化进位为1\n",
    "        prev = None  # 用于记录上一个节点\n",
    "        while current is not None:\n",
    "            current.val += carry       # 将当前节点的值加上进位\n",
    "            carry = current.val // 10  # 计算新的进位\n",
    "            current.val %= 10          # 更新当前节点的值，确保在0-9的范围内\n",
    "            if carry == 0:\n",
    "                break    # 如果没有进位，则结束循环\n",
    "            prev = current    # 更新上一个节点为当前节点\n",
    "            current = current.next  # 更新当前节点为下一个节点\n",
    "\n",
    "        if carry == 1:\n",
    "            prev.next = ListNode(1)   # 如果最高位有进位，添加一个值为1的新节点\n",
    "\n",
    "        # Step 3: Reverse the linked list back\n",
    "        prev = None\n",
    "        current = reversed_head\n",
    "        while current is not None:\n",
    "            next_node = current.next  # 保存当前节点的下一个节点\n",
    "            current.next = prev       # 将当前节点的下一个节点指向前一个节点，实现逆序(恢复原顺序)\n",
    "            prev = current            # 更新前一个节点为当前节点\n",
    "            current = next_node       # 更新当前节点为下一个节点\n",
    "\n",
    "        return prev\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "\n",
    "\n",
    "\n",
    "        def reverse(node):\n",
    "\n",
    "            dummyHead = ListNode()\n",
    "            cur = node\n",
    "            while cur:\n",
    "                next_ = cur.next\n",
    "                cur.next = dummyHead.next\n",
    "                dummyHead.next = cur\n",
    "                cur = next_\n",
    "            return dummyHead.next\n",
    "\n",
    "        reHead = reverse(head)\n",
    "        dummyHead = ListNode(-1, reHead)\n",
    "        plus = 1\n",
    "        pre = dummyHead\n",
    "        cur = reHead\n",
    "        while plus and cur:\n",
    "            next_plus = 1 if (cur.val + plus) >= 10 else 0\n",
    "            cur.val = (cur.val + plus) % 10\n",
    "            plus = next_plus\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        if plus:\n",
    "            pre.next = ListNode(1)\n",
    "        \n",
    "        return reverse(reHead)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        #哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        #找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "        \n",
    "        #最右边的非九位数加1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        #将所有9设置为0\n",
    "        while not_nine:\n",
    "            not_nine.val  = 0\n",
    "            not_nine = not_nine.next\n",
    "        \n",
    "        return sentinel if sentinel.val else sentinel.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        fast = head\n",
    "        slow = ListNode()\n",
    "        slow.next = head\n",
    "        while fast:\n",
    "            if fast.val != 9:\n",
    "                slow = fast\n",
    "            fast = fast.next\n",
    "        slow.val += 1\n",
    "        cur = ListNode()\n",
    "        cur = slow.next\n",
    "        while cur:\n",
    "            cur.val = 0\n",
    "            cur = cur.next\n",
    "        return slow if slow.next == head else head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        \n",
    "        def backtrack(root):\n",
    "            if not root.next:\n",
    "                carry,root.val=(root.val+1)//10,(root.val+1)%10\n",
    "                return carry\n",
    "            carry=backtrack(root.next)\n",
    "\n",
    "            carry,root.val=(root.val+carry)//10,(root.val+carry)%10\n",
    "            return carry\n",
    "        carry=backtrack(head)\n",
    "        if carry:\n",
    "            t=ListNode(1)\n",
    "            t.next=head\n",
    "            head=t\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "        \n",
    "        not_nine.val += 1\n",
    "\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        special = dummy\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val != 9:\n",
    "                special = cur\n",
    "            cur = cur.next\n",
    "        special.val += 1\n",
    "        cur = special.next\n",
    "        while cur:\n",
    "            cur.val = 0\n",
    "            cur = cur.next\n",
    "        if dummy.val == 0:\n",
    "            return head\n",
    "        else:\n",
    "            return dummy\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        new_head = ListNode(0)\n",
    "        new_head.next = head\n",
    "        before_9 = None\n",
    "        cur = new_head\n",
    "        while cur.next:\n",
    "            if cur.next.val == 9:\n",
    "                if not before_9:\n",
    "                    before_9 = cur\n",
    "            else:\n",
    "                before_9 = None\n",
    "            cur = cur.next\n",
    "        if before_9:\n",
    "            before_9.val += 1\n",
    "            while before_9.next:\n",
    "                before_9 = before_9.next\n",
    "                before_9.val = 0\n",
    "        else:\n",
    "            cur.val += 1\n",
    "        return new_head if new_head.val > 0 else new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        end = head\n",
    "        carry = 0\n",
    "        stack = []\n",
    "\n",
    "        while end.next != None:\n",
    "            stack.append(end)\n",
    "            end = end.next\n",
    "        \n",
    "        # stack.append(end)\n",
    "        if end.val + 1 > 9:\n",
    "            carry = 1\n",
    "        end.val = (end.val + 1) % 10\n",
    "\n",
    "        while stack and carry > 0:\n",
    "            cur = stack.pop()\n",
    "            temp = (cur.val + carry) % 10\n",
    "            carry = (cur.val + carry) // 10\n",
    "            cur.val = temp\n",
    "        \n",
    "        if carry > 0:\n",
    "            new_head = ListNode(1)\n",
    "            new_head.next = head\n",
    "            return new_head\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        snetinel = ListNode(0)\n",
    "        snetinel.next = head\n",
    "        non_nine = snetinel \n",
    "\n",
    "        while head:\n",
    "            if head.val !=9:\n",
    "                non_nine = head \n",
    "            head = head.next\n",
    "        non_nine.val += 1\n",
    "        non_nine = non_nine.next \n",
    "\n",
    "        while non_nine:\n",
    "            non_nine.val = 0\n",
    "            non_nine = non_nine.next\n",
    "        return snetinel if snetinel.val else snetinel.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        def reverse(head):\n",
    "            if not head or (not head.next):\n",
    "                return head\n",
    "            else:\n",
    "                cur = head\n",
    "                pre = None\n",
    "                while cur:\n",
    "                    tmp = cur.next\n",
    "                    cur.next = pre\n",
    "                    pre = cur\n",
    "                    cur = tmp\n",
    "                return pre\n",
    "        cur = reverse(head)\n",
    "        head = cur\n",
    "        head.val+=1\n",
    "        while head and head.val>=10:\n",
    "            head.val-=10\n",
    "            if head.next:\n",
    "                head.next.val+=1\n",
    "            else:\n",
    "                head.next=ListNode(1)\n",
    "            head = head.next\n",
    "        return reverse(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        fast = head\n",
    "        slow = ListNode(0,head)\n",
    "        pre = slow\n",
    "        while fast:\n",
    "            if fast.val!=9:\n",
    "                slow = fast\n",
    "            fast=fast.next\n",
    "        slow.val+=1\n",
    "        cur = slow.next\n",
    "        while cur:\n",
    "            cur.val=0\n",
    "            cur = cur.next\n",
    "        return pre if pre.val>0 else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num=0\n",
    "        while head:\n",
    "            num*=10\n",
    "            num+=head.val\n",
    "            head=head.next\n",
    "        num+=1\n",
    "        newhead=ListNode(0)\n",
    "        endnode=newhead\n",
    "        for j in str(num):\n",
    "            cur=ListNode(int(j))\n",
    "            endnode.next=cur\n",
    "            endnode=cur\n",
    "        return newhead.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        def plus(node):\n",
    "            if not node:\n",
    "                return 1\n",
    "            \n",
    "            carry = plus(node.next)\n",
    "            ret, node.val = (node.val + carry) // 10, (node.val + carry) % 10\n",
    "            return ret\n",
    "        \n",
    "        carry = plus(head)\n",
    "        if carry:\n",
    "            return ListNode(1, head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        if sentinel.val:\n",
    "            return sentinel\n",
    "        else:\n",
    "            return sentinel.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        reversed_head = self.reverseLL(head)\n",
    "        cur = reversed_head\n",
    "        while cur:\n",
    "            if cur.val == 9:\n",
    "                cur.val = 0\n",
    "                if not cur.next:\n",
    "                    cur.next = ListNode(1)\n",
    "                    break\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                cur.val += 1\n",
    "                break\n",
    "        reversed_reversed_head = self.reverseLL(reversed_head)\n",
    "        return reversed_reversed_head\n",
    "        \n",
    "    \n",
    "    def reverseLL(self, head):\n",
    "        if not head.next:\n",
    "            return head\n",
    "        cur = head\n",
    "        new_head = head.next\n",
    "        cur.next = None\n",
    "        while new_head:\n",
    "            tmp = new_head\n",
    "            new_head = new_head.next\n",
    "            tmp.next = cur\n",
    "            cur = tmp\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num = 0\n",
    "        p = head\n",
    "\n",
    "        i = 1\n",
    "        while p:\n",
    "            num = num*10+p.val\n",
    "            i *=10\n",
    "            p = p.next\n",
    "\n",
    "        num +=1\n",
    "\n",
    "        p = head\n",
    "        num = (str(num))\n",
    "        pre = None\n",
    "        while p:\n",
    "            p.val = int(num[0])\n",
    "            num = num[1:]\n",
    "            pre = p\n",
    "            p = p.next\n",
    "\n",
    "        if len(num) > 0:\n",
    "            pre.next = ListNode(val=int(num[0]))\n",
    "\n",
    "        return head\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        \n",
    "        notNine = sentinel\n",
    "\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                notNine = head\n",
    "            head = head.next\n",
    "        \n",
    "        notNine.val += 1\n",
    "        notNine = notNine.next\n",
    "        while notNine:\n",
    "            notNine.val = 0\n",
    "            notNine = notNine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        L = []\n",
    "        while head:\n",
    "            L.append(head.val)\n",
    "            head = head.next\n",
    "        carry = 0\n",
    "        n = len(L)\n",
    "        L[-1] += 1\n",
    "        for i in range(len(L) - 1, -1, -1):\n",
    "            L[i] += carry\n",
    "            if L[i] > 9:\n",
    "                L[i] -= 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "        if carry:\n",
    "            L = [1] + L \n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        for i in L:\n",
    "            cur.next = ListNode(i)\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        if not head.next:\n",
    "            #length=1\n",
    "            if head.val<9:\n",
    "                head.val+=1\n",
    "                return head\n",
    "            else:\n",
    "                pre=ListNode(1,head)\n",
    "                head.val=0\n",
    "                return pre\n",
    "\n",
    "        def reverseList(input_head):\n",
    "            pre, cur= None, input_head\n",
    "            while cur:\n",
    "                temp=cur.next\n",
    "                cur.next,pre,cur = pre, cur, temp\n",
    "            return pre\n",
    "        \n",
    "        cur=reverseList(head)\n",
    "        print(\"cur:\", cur)\n",
    "        dummy=ListNode(-1,cur)\n",
    "        cur=dummy.next\n",
    "        cur.val+=1\n",
    "        while cur:\n",
    "            if cur.val<=9:\n",
    "                cur=cur.next\n",
    "            else:\n",
    "                cur.val=0\n",
    "                if cur.next:\n",
    "                    cur.next.val+=1\n",
    "                    cur=cur.next\n",
    "                else:\n",
    "                    newHead = ListNode(1,None)\n",
    "                    cur.next=newHead\n",
    "                    # break\n",
    "        \n",
    "        # print(\"dummy:\", dummy)\n",
    "        # res=reverseList(dummy.next)\n",
    "        # print(res)\n",
    "        return reverseList(dummy.next)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        def pohook(head: ListNode) -> bool:\n",
    "            if not head:\n",
    "                return True\n",
    "            head.val += pohook(head.next)\n",
    "            res = head.val//10\n",
    "            head.val%=10\n",
    "            return res\n",
    "        res = pohook(head)\n",
    "        if res:\n",
    "            new_head = ListNode(1,head)\n",
    "            return new_head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        rev = None\n",
    "        while head.next:\n",
    "            rev, head.next, head = head, rev, head.next\n",
    "        c, head.val = divmod(head.val + 1, 10)\n",
    "        while rev:\n",
    "            c, rev.val = divmod(rev.val + c, 10)\n",
    "            head, rev.next, rev = rev, head, rev.next\n",
    "        return ListNode(1, head) if c else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution(object):\n",
    "    def plusOne(self, head):\n",
    "        st = []\n",
    "        while head:\n",
    "            st.append(head.val)\n",
    "            head = head.next\n",
    "        carry = 0\n",
    "        dummy = ListNode(0)\n",
    "        adder = 1\n",
    "        while st or adder != 0 or carry > 0:\n",
    "            digit = st.pop() if st else 0\n",
    "            sum = digit + adder + carry\n",
    "            carry = 1 if sum >= 10 else 0\n",
    "            sum = sum - 10 if sum >= 10 else sum\n",
    "            cur = ListNode(sum)\n",
    "            cur.next = dummy.next\n",
    "            dummy.next = cur\n",
    "            adder = 0\n",
    "        return dummy.next\n",
    "\n",
    "# 作者：负雪明烛\n",
    "# 链接：https://leetcode.cn/problems/plus-one-linked-list/solutions/1077267/fu-xue-ming-zhu-qiu-jia-fa-xiang-xi-tu-j-rrs3/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "      node = head\n",
    "      if head.val == 9:\n",
    "        while node.next != None and node.next.val == 9:\n",
    "          node = node.next\n",
    "        if node.next == None:\n",
    "          head = ListNode(1, head)\n",
    "          node = head.next\n",
    "          while node != None:\n",
    "            node.val = 0\n",
    "            node = node.next\n",
    "          return head\n",
    "\n",
    "      \n",
    "      while node.next != None:\n",
    "        prev9 = node\n",
    "        while node.next != None and node.next.val == 9:\n",
    "          node = node.next\n",
    "        if node.next == None:\n",
    "          prev9.val += 1\n",
    "          node = prev9.next\n",
    "          while node != None:\n",
    "            node.val = 0\n",
    "            node = node.next\n",
    "          return head\n",
    "        else:\n",
    "          node = node.next\n",
    "      node.val += 1\n",
    "      return head\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        stack = []\n",
    "        while head:\n",
    "            stack.append(head.val)\n",
    "            head = head.next\n",
    "        carry = 0\n",
    "        add = 1\n",
    "        dummy = ListNode(0)\n",
    "        while stack or add != 0 or carry != 0:\n",
    "            tmp = stack.pop() if stack else 0\n",
    "            sums = tmp + add + carry\n",
    "            carry = 1 if sums >= 10 else 0\n",
    "            sums = sums - 10 if sums >= 10 else sums\n",
    "            node = ListNode(sums)\n",
    "            node.next = dummy.next\n",
    "            dummy.next = node\n",
    "            add = 0\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        p = head\n",
    "        num = []\n",
    "        while p:\n",
    "            num.append(p.val)\n",
    "            p = p.next\n",
    "        n = len(num)\n",
    "        stop = n-1\n",
    "        while stop > -1 and num[stop] == 9:\n",
    "            stop -= 1\n",
    "        if stop == -1:\n",
    "            p = head\n",
    "            head = ListNode(1)\n",
    "            head.next = p\n",
    "            while p:\n",
    "                p.val = 0\n",
    "                p = p.next\n",
    "        else:\n",
    "            cur = 0\n",
    "            p = head\n",
    "            while p:\n",
    "                if cur == stop:\n",
    "                    p.val += 1\n",
    "                if cur > stop:\n",
    "                    p.val = 0\n",
    "                p = p.next\n",
    "                cur += 1\n",
    "        return head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        \n",
    "        def backtrack(root):\n",
    "            if not root.next:\n",
    "                carry,root.val=(root.val+1)//10,(root.val+1)%10\n",
    "                return carry\n",
    "            carry=backtrack(root.next)\n",
    "\n",
    "            carry,root.val=(root.val+carry)//10,(root.val+carry)%10\n",
    "            return carry\n",
    "        carry=backtrack(head)\n",
    "        if carry:\n",
    "            t=ListNode(1)\n",
    "            t.next=head\n",
    "            head=t\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        b = 0\n",
    "        for i, x in enumerate(digits):\n",
    "            b += x*(10**(len(digits) - i - 1))\n",
    "        b += 1\n",
    "        b1 = str(b)\n",
    "        b2 = []\n",
    "        for i, y in enumerate(b1):\n",
    "            b2.append(int(y))\n",
    "        return b2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=66 lang=python3\n",
    "#\n",
    "# [66] 加一\n",
    "#\n",
    "# https://leetcode-cn.com/problems/plus-one/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (37.22%)\n",
    "# Total Accepted:    35.4K\n",
    "# Total Submissions: 95.1K\n",
    "# Testcase Example:  '[1,2,3]'\n",
    "#\n",
    "# 给定一个 由整数组成的 非空数组所表示的非负整数，在该数的基础上加一。\n",
    "#\n",
    "# 最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。\n",
    "#\n",
    "# 你可以假设除了整数 0 之外，这个整数不会以零开头。\n",
    "#\n",
    "# 示例 1:\n",
    "#\n",
    "# 输入: [1,2,3]\n",
    "# 输出: [1,2,4]\n",
    "# 解释: 输入数组表示数字 123。\n",
    "#\n",
    "#\n",
    "# 示例 2:\n",
    "#\n",
    "# 输入: [4,3,2,1]\n",
    "# 输出: [4,3,2,2]\n",
    "# 解释: 输入数组表示数字 4321。\n",
    "#\n",
    "#\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        digits = int(''.join([str(x) for x in digits]))\n",
    "        digits += 1\n",
    "        return [int(x) for x in str(digits)]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: 'List[int]') -> 'List[int]':\n",
    "        n = len(digits)\n",
    "        i = n - 1\n",
    "        carry = 1\n",
    "        while i >= 0 and carry:\n",
    "            r = (carry + digits[i]) % 10\n",
    "            carry = (carry + digits[i]) // 10\n",
    "            digits[i] = r\n",
    "            i -= 1\n",
    "        if carry:\n",
    "            digits.insert(0, 1)\n",
    "        return digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        length = len(digits)\n",
    "        num = 0\n",
    "        for i in range(len(digits)):\n",
    "            print(digits[i])\n",
    "            num += digits[i]*pow(10,length-i-1)\n",
    "        num += 1\n",
    "\n",
    "        return [int(x) for x in str(num)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        length = len(digits)\n",
    "        index = length-1\n",
    "        last = digits[index]\n",
    "        while last+1 == 10:\n",
    "            result.insert(0, 0)\n",
    "            index -= 1\n",
    "            if index == -1:\n",
    "                index += 1\n",
    "                digits.insert(0, 0)\n",
    "            last = digits[index]\n",
    "        digits[index] += 1\n",
    "        result = digits[:index+1]+result\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        carry = 1\n",
    "        for i in range(len(digits) - 1, -1, -1):\n",
    "            num = (digits[i] + carry)\n",
    "            digits[i] = num % 10\n",
    "            carry = num // 10\n",
    "        if carry == 1:\n",
    "            digits.insert(0, 1)\n",
    "        return digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        if len(digits) ==0:\n",
    "            digits = [1]\n",
    "        elif digits[-1] == 9:\n",
    "            digits = self.plusOne(digits[:-1])\n",
    "            digits.extend([0])\n",
    "        else:\n",
    "            digits[-1] +=1\n",
    "        return digits\n",
    "    \n",
    "    \n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        digits[-1] += 1\n",
    "        if digits[-1] == 10:\n",
    "            len_digit = len(digits)\n",
    "            if len_digit >= 2:\n",
    "                digits[-1] = 0\n",
    "                print(-len_digit)\n",
    "                for el in range(-2, -len_digit - 1,-1):\n",
    "                    digits[el] += 1\n",
    "                    print(digits[el])\n",
    "                    if digits[el] != 10:\n",
    "                        break\n",
    "                    else:\n",
    "                        digits[el] = 0\n",
    "                        if el == -len_digit:\n",
    "                            digits.insert(0,1)\n",
    "            else:\n",
    "                return [1, 0]\n",
    "        return digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        for i in range(len(digits)-1,-1,-1):\n",
    "            if digits[i] < 9:\n",
    "                digits[i] += 1\n",
    "                return digits\n",
    "            else:\n",
    "                digits[i] = 0\n",
    "        return [1]+digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        return [int(x) for x in str(int(''.join([str(x) for x in digits])) + 1)]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # 得到整数的位数\n",
    "        length = len(digits)\n",
    "        # 将非空数组合并成一个整数\n",
    "        num = 0\n",
    "        for i in range(length):\n",
    "            num += digits[i]*10**(length-1-i)\n",
    "        # 加1得到新的结果\n",
    "        num += 1\n",
    "        # 将结果转换成字符串\n",
    "        strNum = str(num)\n",
    "        # 再将字符串转换成整数数组\n",
    "        res = [int(char) for char in strNum]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        num_str = \"\"\n",
    "        for digit in digits:\n",
    "            num_str += str(digit)\n",
    "        num = int(num_str) + 1\n",
    "        num_str = str(num)\n",
    "        new_digits = []\n",
    "        for char in num_str:\n",
    "            new_digits.append(int(char))\n",
    "\n",
    "        return new_digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        digits_s = [str(x) for x in digits]\n",
    "        digits_i = int(''.join(digits_s)) + 1\n",
    "        digits_r = [int(x) for x in str(digits_i)]\n",
    "        return digits_r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        num_str = \"\"\n",
    "        for digit in digits:\n",
    "            num_str += str(digit)\n",
    "        num = int(num_str) + 1\n",
    "        num_str = str(num)\n",
    "        new_digits = []\n",
    "        for char in num_str:\n",
    "            new_digits.append(int(char))\n",
    "\n",
    "        return new_digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        # _len = len(digits) - 1\n",
    "        # idx = 0\n",
    "        # res = 0\n",
    "        # while _len >= 0:\n",
    "        #     res += digits[idx] * 10 ** _len\n",
    "        #     _len -= 1\n",
    "        #     idx += 1\n",
    "        # return list(map(int, str(res + 1)))\n",
    "        # num = int(''.join(map(str, digits)))\n",
    "        # return [int(x) for x in str(num + 1)]#list(map(int, str(num + 1)))\n",
    "        sums = 0\n",
    "        for i in digits:\n",
    "            sums = sums * 10 + i #10进制乘以10，进行累和；\n",
    "        sums_str = str(sums + 1)\n",
    "        return [int(j) for j in sums_str]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        sum = 0\n",
    "        for ii in digits:\n",
    "            sum=sum*10+ii\n",
    "        sum+=1\n",
    "        anw=[]\n",
    "        sss=len(str(sum))\n",
    "        for i in range(sss):\n",
    "            anw.append(sum%10)\n",
    "            sum=sum//10\n",
    "        return reversed(anw)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def unitPlusOne(self,n):\n",
    "        if n + 1 == 10:\n",
    "            return 0\n",
    "        else:\n",
    "            return n + 1\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        result = digits\n",
    "        i = len(digits) - 1\n",
    "        while i > -1:\n",
    "            tmp = self.unitPlusOne(digits[i])\n",
    "            result[i] = tmp\n",
    "            if tmp == 0:\n",
    "                i = i - 1\n",
    "            else:\n",
    "                break\n",
    "        if i == -1:\n",
    "            return [1] + result\n",
    "        else:\n",
    "            return result\n",
    "            \n",
    "                \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        digits[-1] += 1\n",
    "        # if digits[0] == 10:\n",
    "        #     digits[0] = 0\n",
    "        #     digits.insert(0, 1)\n",
    "        #     return digits\n",
    "        for i in range(len(digits)-1, 0, -1):\n",
    "            if digits[i] == 10:\n",
    "                digits[i] = 0\n",
    "                digits[i-1] += 1\n",
    "                if digits[i-1] != 10 and i != 1:\n",
    "                    return digits\n",
    "        if digits[0] == 10:\n",
    "            digits[0] = 0\n",
    "            digits.insert(0, 1)\n",
    "            return digits\n",
    "        return digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        carry = 1\n",
    "        for ind in range(len(digits)-1, -1, -1):\n",
    "            if digits[ind] < 9:\n",
    "                digits[ind] += 1\n",
    "                return digits\n",
    "            digits[ind] = 0\n",
    "\n",
    "        res = [1] + [0]*len(digits)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        digits.reverse()\n",
    "        digits[0]+=1\n",
    "        L=len(digits)\n",
    "        for i in range(L):\n",
    "            if digits[i]!=10:\n",
    "                break\n",
    "            else:\n",
    "                digits[i]=0\n",
    "                if i<L-1:\n",
    "                    digits[i+1]+=1\n",
    "                else:\n",
    "                    digits.append(1)\n",
    "        digits.reverse()\n",
    "        return digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        newlst = []\n",
    "        while digits and digits[-1] == 9:\n",
    "            digits.pop()\n",
    "            newlst.append(0)\n",
    "        if not digits:\n",
    "            return [1] + newlst\n",
    "        else:\n",
    "            digits[-1] += 1\n",
    "            return digits + newlst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        if sum(digits) == 0:\n",
    "            digits[-1] += 1\n",
    "            return digits\n",
    "        return [int(j) for j in (int(''.join([str(i) for i in digits])) + 1).__str__()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        if sum(digits) == 0:\n",
    "            digits[-1] += 1\n",
    "            return digits\n",
    "        return [int(j) for j in (int(''.join([str(i) for i in digits])) + 1).__str__()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "from itertools import *\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        number = reduce(lambda x,y:10*x+y,digits)+1\n",
    "        s = [int(i) for i in str(number)]\n",
    "        s = [0]*(len(digits)-len(s))+s\n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        if not digits:\n",
    "            return\n",
    "        l = len(digits)\n",
    "        digits[l-1] += 1\n",
    "        print(l, digits)\n",
    "        for i in range(l-1,-1,-1):\n",
    "            print(\"c\")\n",
    "            print(i, digits[i])\n",
    "            if digits[i] == 10:\n",
    "                digits[i] = 0\n",
    "                if i>0:\n",
    "                    print(\"a\")\n",
    "                    digits[i-1] += 1\n",
    "                else:\n",
    "                    print(\"b\")\n",
    "                    digits = [1] + digits\n",
    "        return digits\n",
    "            \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        num=0\n",
    "        for digit in digits:\n",
    "            num=num*10+digit \n",
    "        num+=1\n",
    "        tnum=str(num)\n",
    "        tdigits=[]\n",
    "        for j in range(len(tnum)):\n",
    "            tdigits.append(int(tnum[j]))\n",
    "        return tdigits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        for i in range(1, len(digits)+1):\n",
    "            if digits[-i]+1 == 10:\n",
    "                digits[-i] = 0\n",
    "            else:\n",
    "                digits[-i] += 1\n",
    "                return digits\n",
    "        return [1] + digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        n = len(digits)\n",
    "        add = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i == n - 1:\n",
    "                digits[i] += 1\n",
    "            if digits[i] + add > 9:\n",
    "                digits[i] = 0\n",
    "                add = 1\n",
    "            else:\n",
    "                digits[i] += add\n",
    "                add = 0\n",
    "        \n",
    "        if add == 1:\n",
    "            digits.insert(0, 1)\n",
    "        \n",
    "        return digits\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        temp=[]\n",
    "        res=[]\n",
    "        for i in range(len(digits)):\n",
    "            temp.append(str(digits[i]))\n",
    "        \n",
    "        str_di=\"\".join(temp)\n",
    "        int_di=int(str_di)\n",
    "        addone=int_di+1\n",
    "        for d in str(addone):\n",
    "            res.append(int(d))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def plusOne(self, digits):\r\n",
    "\r\n",
    "        # return [int(j) for j in list(str(int(''.join([str(i) for i in digits])) + 1))]\r\n",
    "\r\n",
    "        # num = sum([digits[i] * (10**(len(digits) - i - 1)) for i in range(len(digits))]) + 1\r\n",
    "\r\n",
    "        # index = -1\r\n",
    "        # num = 0\r\n",
    "        # while True:\r\n",
    "        #     if -index > len(digits):\r\n",
    "        #         if num != 0:\r\n",
    "        #             digits.insert(0, num)\r\n",
    "        #         return digits\r\n",
    "        #     if digits[index] + 1 < 10:\r\n",
    "        #         if num == 0:\r\n",
    "        #             digits[index] = digits[index] + 1\r\n",
    "        #         else:\r\n",
    "        #             digits[index] = digits[index] + num\r\n",
    "        #         return digits\r\n",
    "        #     else:\r\n",
    "        #         num = (digits[index] + 1) // 10\r\n",
    "        #         digits[index] = (digits[index] + 1) % 10\r\n",
    "        #         index -= 1        \r\n",
    "        \r\n",
    "        add_one = False\r\n",
    "        index = -1\r\n",
    "        while True:\r\n",
    "            # print(digits, index)\r\n",
    "            if -index == len(digits):\r\n",
    "                if digits[index] == 9:\r\n",
    "                    digits[index] = 0 \r\n",
    "                    digits.insert(0, 1)\r\n",
    "                else:\r\n",
    "                    digits[index] += 1\r\n",
    "                return digits\r\n",
    "\r\n",
    "            if add_one:\r\n",
    "                if digits[index] == 9:\r\n",
    "                    digits[index] = 0\r\n",
    "                    index -= 1\r\n",
    "                else:\r\n",
    "                    digits[index] += 1\r\n",
    "                    return digits    \r\n",
    "                continue\r\n",
    "\r\n",
    "            if index == -1:\r\n",
    "                if digits[index] == 9:\r\n",
    "                    digits[index] = 0 \r\n",
    "                    add_one = True\r\n",
    "                    index -= 1\r\n",
    "                    continue\r\n",
    "                else:\r\n",
    "                    digits[index] += 1\r\n",
    "                    return digits\r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "from curses.ascii import SO\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def method1(self, digits: List[int]) -> List[int]:\n",
    "        next_rvs_digits = []\n",
    "\n",
    "        rvs_digits = reversed(digits)\n",
    "\n",
    "        is_over = True\n",
    "        for d in rvs_digits:\n",
    "            if is_over:\n",
    "                if d == 9:\n",
    "                    next_rvs_digits.append(0)\n",
    "\n",
    "                    is_over = True\n",
    "                else:\n",
    "                    next_rvs_digits.append(d + 1)\n",
    "\n",
    "                    is_over = False\n",
    "            else:\n",
    "                next_rvs_digits.append(d)\n",
    "\n",
    "                is_over = False\n",
    "\n",
    "        if is_over:\n",
    "            next_rvs_digits.append(1)\n",
    "\n",
    "        return list(reversed(next_rvs_digits))\n",
    "\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        return self.method1(digits)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    slt = Solution()\n",
    "    print(list(slt.plusOne([1,2,3])))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        b = \"\"\n",
    "        for i in digits:\n",
    "            b += str(i)\n",
    "        b = int(b) +1\n",
    "        b = str(b)\n",
    "        c = []\n",
    "        for i in b:\n",
    "            i = int(i)\n",
    "            c.append(i)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        n = len(digits)\n",
    "        add = 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            tmp = digits[i] + add\n",
    "            digits[i] = tmp % 10\n",
    "            add = tmp // 10\n",
    "        if add == 1:\n",
    "            digits = [1] + digits\n",
    "        return digits\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        digits.reverse()\n",
    "        carry = 0\n",
    "        for i in range(len(digits)):\n",
    "            if i == 0:\n",
    "                digits[i] = digits[i] + carry + 1\n",
    "            else:\n",
    "                digits[i] = digits[i] + carry\n",
    "            carry = 0\n",
    "            if digits[i] >= 10:\n",
    "                digits[i] -= 10\n",
    "                carry = 1\n",
    "        if carry == 1:\n",
    "            digits.append(1)\n",
    "        digits.reverse()\n",
    "        return digits"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
